// https://www.lintcode.com/problem/construct-binary-tree-from-preorder-and-inorder-traversal/description?_from=ladder&&fromId=6

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param inorder: A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     */
     
    // 从前序的结果里找到根节点；
    // 再从中序的结果里找到左右子树，并获取左右子树中节点的个数；
    typedef vector<int>::iterator Iter;
    TreeNode * recBuildTree(Iter pbegin, Iter pend, Iter ibegin, Iter iend)
    {
        if (pbegin == pend) return NULL;
        TreeNode * root = new TreeNode(*pbegin);
        Iter node = find(ibegin, iend, *pbegin);
        root->left = recBuildTree(pbegin + 1, pbegin + 1 + (node - ibegin), ibegin, node); //注意指针相减加括号
        root->right = recBuildTree(pbegin + 1 + (node - ibegin), pend, node + 1, iend);
        return root;
    }
    TreeNode * buildTree(vector<int> preorder, vector<int> inorder) {
        return recBuildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
};

class Solution {
public:
    TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder, int pre_left, int pre_right, int in_left, int in_right, unordered_map<int, int>& index) {
        if (pre_left > pre_right) return NULL;
        int pre_root = pre_left;
        TreeNode* root = new TreeNode(preorder[pre_root]);
        int in_root = index[preorder[pre_root]];
        int size_left_subtree = in_root - in_left;
        root->left = myBuildTree(preorder, inorder, pre_left + 1, pre_left + size_left_subtree, in_left, in_root - 1, index);
        root->right = myBuildTree(preorder, inorder, pre_left + size_left_subtree + 1, pre_right, in_root + 1, in_right, index);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        unordered_map<int, int> index;
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1, index);
    }
};